package graph.vote;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class 找到小镇的法官_997 {
// 图论问题的两种解法
            public int findJudge_vote(int n, int[][] trust) {
                // 投票法  有一个人不能给其他人投票  但是其他人都要给自己投票 共 n-1张 找到那个人 
                int[] vote = new int[n + 1]; // 因为编号下标是从1开始的 防止要转换
                for(int[] tmp : trust) {
                    vote[tmp[0]] --; // 谁投过票 --保证 自身就不可能有 n- 1张票
                    vote[tmp[1]] ++;
                }

                for(int i = 1; i< n + 1; i++) {
                    if(vote[i] == n -1) {
                        return i;
                    }
                }
                return -1;
            }

            
            // 双map解决图类问题  出度入度 本题简化入度为set
             public int findJudge_出入度统计(int n, int[][] trust) {
                // 可能是法官的人
                HashSet<Integer> people = new HashSet<>();
                // 每个人的被信任度
                Map<Integer,Integer> map = new HashMap<>();
                // 初始化people
                for (int i = 1; i < n + 1; i++) {
                    people.add(i);
                }
                for(int[] tmp : trust) {
                   people.remove(tmp[0]);
                   map.put(tmp[1], map.getOrDefault(tmp[1], 0) + 1);
                }
                
                if(people.size() == 1) {
                    int person = people.iterator().next();
                    if(map.getOrDefault(person, 0) == n - 1)  // getOrDefault是防止出现找不到为空的情况  产生null == n-1 抛异常
                    return person;
                }
                return -1;
            }
        }
